package leetcode.lcp.lcp20220423;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

import leetcode.IDebug;
import leetcode.helper.H;

public class Solution3 implements IDebug {

	List<Integer> times;
	Map<Integer, Integer> timeIdx;
	List<Integer[]>[] map;
	int size;

	public int getMaximumNumber(int[][] moles) {
		Set<Integer> set = new HashSet<Integer>();
		set.add(0);
		for (int i = 0; i < moles.length; i++) {
			set.add(moles[i][0]);
		}
		times = new ArrayList<>(set);
		Collections.sort(times);
		timeIdx = new HashMap<>();
		for (int i = 0; i < times.size(); i++) {
			timeIdx.put(times.get(i), i);
		}
		size = times.size();
		map = new ArrayList[size];
		for (int i = 0; i < map.length; i++) {
			map[i] = new ArrayList<>();
		}
		for (int i = 0; i < moles.length; i++) {
			int[] mole = moles[i];
			int t = mole[0], x = mole[1], y = mole[2];
			int idx = timeIdx.get(t);
			map[idx].add(new Integer[] { x, y });
		}

//		Integer[][][] dp = new Integer[9][size + 1][size + 1];
		Map<Integer, Map<Integer, Map<Integer, Integer>>> dp = new HashMap<>();
		return find(0, 1, 1, 0, dp);
	}

	public int index(int i, int j) {
		return i * 3 + j;
	}

	private int find(int start, int sx, int sy, int index, Map<Integer, Map<Integer, Map<Integer, Integer>>> dp
//			,Integer[][][] dp
	) {
		if (index == size) {
			return 0;
		}
		int hash = index(sx, sy);
		if (dp.containsKey(hash)) {
			if (dp.get(hash).containsKey(start)) {
				if (dp.get(hash).get(start).containsKey(index)) {
					return dp.get(hash).get(start).get(index);
				}
			}
		}

//		if (dp[hash][start][index] != null) {
//			return dp[hash][start][index];
//		}
		int ans = this.find(start, sx, sy, index + 1, dp);
		int startTime = times.get(start);
		int indexTime = times.get(index);
		List<Integer[]> moles = map[index];
		for (int i = 0; i < moles.size(); i++) {
			Integer[] mole = moles.get(i);
			int ex = mole[0], ey = mole[1];
			if (this.dist(sx, sy, ex, ey) <= indexTime - startTime) {
				ans = Math.max(ans, this.find(index, ex, ey, index + 1, dp) + 1);
			}
		}
//		dp[hash][start][index] = ans;
		Map map1 = new HashMap<>();
		map1.put(index, ans);
		Map map2 = new HashMap<>();
		map2.put(start, map1);
		dp.put(hash, map2);
		return ans;
	}

	private int dist(int sx, int sy, int ex, int ey) {
		return Math.abs(sx - ex) + Math.abs(sy - ey);
	}

	@Override
	public void debug4() {
		H.compare(3, this.getMaximumNumber(H.str2array1("[[2,0,1],[3,0,0],[3,1,0],[2,2,0],[5,1,0],[2,2,1]]")));
		H.compare(2, this.getMaximumNumber(H.str2array1("[[1,1,0],[2,0,1],[4,2,2]]")));
		H.compare(3, this.getMaximumNumber(H.str2array1("[[2,0,2],[5,2,0],[4,1,0],[1,2,1],[3,0,2]]")));
		H.compare(0, this.getMaximumNumber(H.str2array1("[[0,1,0],[0,0,1]]")));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution3 so = new Solution3();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
